
#include <iostream>

#define VNAME(name) (#name)
#define debug(x) ({ auto debugx = x; std::cout << "in." << __LINE__ << "->(" << VNAME(x) << ": " << debugx << ") "; debugx; })
using namespace std;
const int MOD = 571373, R_ = (1 << 30) - 1, N = 1e5 + 5;
typedef long long LL;
struct tr {
    LL lr, value, mul, add;
    inline LL r() { return lr & R_; }
    inline LL l() { return lr >> 32; }
    inline LL set(LL L, LL R, LL v) { this->lr = L << 32 | R; this->mul = 1; return this->value = v; }
}x[N << 4];
int arr[N];
LL build(int i, int l, int r) {
    if (l == r) return x[i].set(l, r, arr[l]); 
    int mid = l + r >> 1;
    return x[i].set(l, r, (build(i << 1, l, mid) + build(i << 1 | 1, mid + 1, r)) % MOD);
}
void dddd(int j) {
    if (x[j].add || x[j].mul != 1) {
        LL k = x[j].mul, add = x[j].add;
        x[j].mul = 1, x[j].add = 0;
        for (int i = j << 1; i <= (j << 1 | 1); ++ i) {
            x[i].value = (x[i].value * k + add * (x[i].r() - x[i].l() + 1)) % MOD;
            x[i].mul = x[i].mul * k % MOD;
            x[i].add = (x[i].add * k + add) % MOD;
        }
    }
}
LL Qmulti(int i, int l, int r, int k, int L, int R) {
    if (L <= l && r <= R) { 
        x[i].value = x[i].value * k % MOD;
        x[i].mul = x[i].mul * k % MOD;
        x[i].add = x[i].add * k % MOD;
    } else {
        dddd(i);
        int mid = l + r >> 1;
        if (L <= mid) Qmulti(i << 1, l, mid, k, L, R);
        if (R > mid) Qmulti(i << 1 | 1, mid + 1, r, k, L, R);
        x[i].value = (x[i << 1].value + x[i << 1 | 1].value) % MOD;
    }
    return x[i].value;
}
LL Qadd(int i, int l, int r, int k, int L, int R) {
    if (L <= l && r <= R) { 
        x[i].value = (x[i].value + k * (r - l + 1))% MOD;
        x[i].add = (x[i].add + k) % MOD;
    } else {
        dddd(i);
        int mid = l + r >> 1;;
        if (L <= mid) Qadd(i << 1, l, mid, k, L, R);
        if (R > mid) Qadd(i << 1 | 1, mid + 1, r, k, L, R);
        x[i].value = (x[i << 1].value + x[i << 1 | 1].value) % MOD;
    }
    return x[i].value;
}
LL Qcheck(int i, int l, int r, int L, int R) {
    if (L <= l && r <= R) 
        return x[i].value;
    dddd(i);
    int mid = l + r >> 1; LL sum = 0;
    if (L <= mid) sum = Qcheck(i << 1, l, mid, L, R);
    if (R > mid) sum += Qcheck(i << 1 | 1, mid + 1, r, L, R);
    return sum % MOD;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m, p;
    cin >> n >> m >> p;
    for (int i = 1; i <= n; ++ i) cin >> arr[i];
    build(1, 1, n);
    char f;
    while (m--) {
        int l, r, k;
        cin >> f >> l >> r;
        if (f == '1') {
            cin >> k;
            Qmulti(1, 1, n, k, l, r);
        } else if (f == '2') {
            cin >> k;
            Qadd(1, 1, n, k, l, r);
        } else {
            cout << Qcheck(1, 1, n, l, r) << endl;
        }
    }
    cout << endl;
    return 0;
}